// NC14 按之字形顺序打印二叉树
// https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
// 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
// 输入 {1,2,3,#,#,4,5}
// 返回值 [[1],[3,2],[4,5]]

#include <deque>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  struct TreeNode* left;
  struct TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//     1
//  2    3
//     4   5

// 出奇层    front[        ->1 ]back  1<-    (1)   进奇层
// 进偶层 ->3->2 front[  3<- 2<-     ]back       (2,3)   出偶层
// 进奇层    front[       ->5->4 ]back  5<-4<-   (4,5)   出奇层

class Solution {
 public:
  vector<vector<int> > Print(TreeNode* pRoot) {
    vector<vector<int> > res;
    if (pRoot == nullptr) {
      return res;
    }
    deque<TreeNode*> deqNode;
    deqNode.push_back(pRoot);
    while (!deqNode.empty()) {
      vector<int> vtOne;
      // 出奇数
      int nQsize = deqNode.size();
      for (int i = 0; i < nQsize; i++) {
        TreeNode* nod = deqNode.back();
        deqNode.pop_back();
        vtOne.push_back(nod->val);
        if (nod->left) deqNode.push_front(nod->left);
        if (nod->right) deqNode.push_front(nod->right);
      }
      res.push_back(vtOne);
      if (deqNode.empty()) break;
      vtOne.clear();
      // 出偶数
      nQsize = deqNode.size();
      for (int i = 0; i < nQsize; i++) {
        TreeNode* nod = deqNode.front();
        deqNode.pop_front();
        vtOne.push_back(nod->val);
        if (nod->right) deqNode.push_back(nod->right);
        if (nod->left) deqNode.push_back(nod->left);
      }
      res.push_back(vtOne);
    }
    return res;
  }
};

int main14() {
  Solution sol;
  sol.Print(nullptr);
  return 0;
}
